"""五子棋AI玩家模块

实现AI决策逻辑，包括评估函数、极小极大搜索和Alpha-Beta剪枝算法
支持不同难度级别设置和性能优化
"""

import copy
import math
import time

# 评分常量（根据威胁程度设置不同分值）
SCORES = {
    "FIVE_IN_A_ROW": 1000000,    # 连五
    "FOUR_OPEN": 100000,         # 活四
    "FOUR_CLOSED": 10000,        # 冲四
    "THREE_OPEN": 1000,          # 活三
    "THREE_CLOSED": 100,         # 冲三
    "TWO_OPEN": 10,              # 活二
    "TWO_CLOSED": 1,             # 冲二
    "ONE": 0                     # 单个棋子
}

# 难度级别配置
DIFFICULTY_CONFIG = {
    "easy": {"min_depth": 1, "max_depth": 2, "max_time": 0.2, "eval_complexity": "low", 
              "prune_factor": 1.0, "max_candidates": 8},
    "normal": {"min_depth": 2, "max_depth": 3, "max_time": 0.5, "eval_complexity": "medium",
               "prune_factor": 0.9, "max_candidates": 12},
    "medium": {"min_depth": 3, "max_depth": 4, "max_time": 0.8, "eval_complexity": "medium-high",
               "prune_factor": 0.8, "max_candidates": 15},
    "hard": {"min_depth": 4, "max_depth": 5, "max_time": 1.0, "eval_complexity": "high",
             "prune_factor": 0.7, "max_candidates": 20},
    "expert": {"min_depth": 5, "max_depth": 6, "max_time": 1.5, "eval_complexity": "highest",
               "prune_factor": 0.6, "max_candidates": 25}
}

class AIPlayer:
    """AI玩家类，负责AI决策逻辑"""
    
    def __init__(self, difficulty="medium"):
        """初始化AI玩家
        
        Args:
            difficulty: 难度级别，可选值："easy", "normal", "medium", "hard", "expert"
        """
        # 验证难度级别
        if difficulty not in DIFFICULTY_CONFIG:
            difficulty = "medium"
            
        self.difficulty = difficulty
        self.config = DIFFICULTY_CONFIG[difficulty]
        self.min_depth = self.config["min_depth"]
        self.max_depth = self.config["max_depth"]
        self.prune_factor = self.config["prune_factor"]
        self.max_candidates = self.config["max_candidates"]
        self.player = 2  # AI默认执白
        self.human_player = 1
        self.board_size = 15  # 15x15棋盘
        self.directions = [(0, 1), (1, 0), (1, 1), (1, -1)]  # 四个方向
        # 置换表，用于缓存已计算的局面
        self.transposition_table = {}
        # 置换表条目标志
        self.TT_EXACT = 0
        self.TT_LOWER = 1
        self.TT_UPPER = 2
        self.use_alpha_beta = True  # 启用Alpha-Beta剪枝
    
    def _get_search_params(self):
        """获取搜索参数
        
        Returns:
            dict: 搜索参数字典
        """
        return {
            "min_depth": self.min_depth,
            "max_depth": self.max_depth,
            "max_time": self.config["max_time"],
            "eval_complexity": self.config["eval_complexity"],
            "prune_factor": self.prune_factor,
            "max_candidates": self.max_candidates
        }
    
    def set_search_depth(self, depth):
        """设置搜索深度
        
        Args:
            depth: 搜索深度
        """
        self.min_depth = max(1, min(6, depth))
        self.max_depth = max(self.min_depth, min(6, depth + 1))
    
    def evaluate_position(self, board, row, col, player):
        """优化版位置评估函数，基于模式匹配的评分系统
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            player: 当前玩家
            
        Returns:
            int: 位置评分
        """
        if board[row][col] != 0:
            # 该位置已有棋子，返回固定分数
            return 100000 if board[row][col] == player else -100000
        
        score = 0
        BOARD_SIZE = len(board)
        
        # 模式评分表
        patterns = {
            # 连五
            (5, 0): 100000,
            # 活四
            (4, 2): 10000,
            # 冲四（一头堵）
            (4, 1): 1000,
            # 活三
            (3, 2): 100,
            # 冲三（一头堵）
            (3, 1): 10,
            # 活二
            (2, 2): 5,
            # 冲二（一头堵）
            (2, 1): 1
        }
        
        # 检查各个方向
        for dr, dc in self.directions:
            line_info = self._analyze_line_pattern(board, row, col, dr, dc, player)
            
            # 检查是否形成特定模式
            if line_info['consecutive'] >= 2:
                pattern_key = (line_info['consecutive'], line_info['open_ends'])
                if pattern_key in patterns:
                    score += patterns[pattern_key]
        
        # 根据难度级别调整防守策略
        if self.config["eval_complexity"] in ["high", "highest"]:
            # 评估对手在此位置的威胁
            opponent_score = 0
            for dr, dc in self.directions:
                line_info = self._analyze_line_pattern(board, row, col, dr, dc, 
                                                     self.human_player if player == self.player else self.player)
                if line_info['consecutive'] >= 2:
                    pattern_key = (line_info['consecutive'], line_info['open_ends'])
                    if pattern_key in patterns:
                        opponent_score += patterns[pattern_key]
            
            # 防守优先级：如果对手威胁更大，提升防守权重
            if opponent_score > score * 1.5:
                score = opponent_score * 1.2
        
        return score
    
    def _analyze_line_pattern(self, board, row, col, dr, dc, player):
        """分析指定方向上的棋型模式
        
        Args:
            board: 当前棋盘状态
            row: 行坐标
            col: 列坐标
            dr: 行方向增量
            dc: 列方向增量
            player: 当前玩家
            
        Returns:
            dict: 包含连续子数量和开放端点信息
        """
        BOARD_SIZE = len(board)
        consecutive = 0
        open_ends = 0
        blocked_ends = 0
        
        # 模拟在空位落子
        original_value = board[row][col]
        board[row][col] = player
        
        # 检查正向
        r, c = row + dr, col + dc
        while 0 <= r < BOARD_SIZE and 0 <= c < BOARD_SIZE:
            if board[r][c] == player:
                consecutive += 1
                r += dr
                c += dc
            else:
                if board[r][c] == 0:
                    open_ends += 1
                else:
                    blocked_ends += 1
                break
        
        # 检查反向
        r, c = row - dr, col - dc
        while 0 <= r < BOARD_SIZE and 0 <= c < BOARD_SIZE:
            if board[r][c] == player:
                consecutive += 1
                r -= dr
                c -= dc
            else:
                if board[r][c] == 0:
                    open_ends += 1
                else:
                    blocked_ends += 1
                break
        
        # 撤销模拟落子
        board[row][col] = original_value
        
        return {
            'consecutive': consecutive + 1,  # +1 包含当前模拟落子
            'open_ends': open_ends,
            'blocked_ends': blocked_ends
        }
    
    def evaluate_board(self, board, player, last_move=None):
        """优化版评估整个棋盘，只评估有效区域
        
        Args:
            board: 棋盘状态
            player: 当前玩家
            last_move: 最后落子位置(row, col)，用于增量评估
            
        Returns:
            int: 棋盘总评分
        """
        # 增量评估
        if last_move is not None:
            return self._evaluate_position_around(board, last_move, player)
        
        # 根据难度级别调整评估复杂度
        eval_complexity = self.config["eval_complexity"]
        
        # 简单难度使用简化评估并引入随机因素
        if eval_complexity == "low":
            score = self._evaluate_board_efficient(board, player)
            # 引入一些随机波动，使AI偶尔犯错
            import random
            score += random.randint(-50, 50)
            return score
        elif eval_complexity == "medium":
            # 中等难度评估有效区域
            return self._evaluate_board_efficient(board, player)
        else:
            # 高级难度更全面评估
            return self._evaluate_board_comprehensive(board, player)
    
    def _evaluate_position_around(self, board, last_move, player):
        """增量评估：只评估指定位置周围的区域
        
        Args:
            board: 当前棋盘状态
            last_move: 最后落子位置(row, col)
            player: 当前玩家
            
        Returns:
            int: 增量评估得分
        """
        row, col = last_move
        score = 0
        
        # 评估最后落子位置及其周围
        for i in range(max(0, row-3), min(self.board_size, row+4)):
            for j in range(max(0, col-3), min(self.board_size, col+4)):
                if board[i][j] != 0:
                    player_at_pos = board[i][j]
                    # 评估该位置在四个方向上的得分
                    for dx, dy in self.directions:
                        line_info = self._analyze_line_pattern(board, i, j, dx, dy, player_at_pos)
                        
                        # 检查是否形成特定模式
                        patterns = {
                            (5, 0): 100000,
                            (4, 2): 10000,
                            (4, 1): 1000,
                            (3, 2): 100,
                            (3, 1): 10,
                            (2, 2): 5,
                            (2, 1): 1
                        }
                        
                        if line_info['consecutive'] >= 2:
                            pattern_key = (line_info['consecutive'], line_info['open_ends'])
                            if pattern_key in patterns:
                                pos_score = patterns[pattern_key]
                                if player_at_pos == player:
                                    score += pos_score
                                else:
                                    score -= pos_score
        
        return score
    
    def _evaluate_board_efficient(self, board, player):
        """高效评估棋盘，只评估有效区域
        
        Args:
            board: 当前棋盘状态
            player: 当前玩家
            
        Returns:
            int: 评估分数
        """
        score = 0
        BOARD_SIZE = len(board)
        evaluated = set()  # 已评估的位置集合
        opponent = self.human_player if player == self.player else self.player
        
        # 只评估已存在棋子的周围区域
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] != 0:
                    # 评估该位置以及周围3格范围内的位置
                    for di in range(-3, 4):
                        for dj in range(-3, 4):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < BOARD_SIZE and 0 <= nj < BOARD_SIZE and (ni, nj) not in evaluated:
                                evaluated.add((ni, nj))
                                if board[ni][nj] == player:  # 己方
                                    position_score = self.evaluate_position(board, ni, nj, player)
                                    score += position_score * 0.5  # 已放置棋子权重降低
                                elif board[ni][nj] == 0:  # 空位
                                    # 评估己方在空位的价值
                                    score += self.evaluate_position(board, ni, nj, player) * 0.8
                                    # 评估对方在空位的威胁
                                    score -= self.evaluate_position(board, ni, nj, opponent) * 0.8
        
        # 如果棋盘几乎为空，给予中心位置额外权重
        if len(evaluated) < 10:
            center = BOARD_SIZE // 2
            for i in range(center - 2, center + 3):
                for j in range(center - 2, center + 3):
                    if 0 <= i < BOARD_SIZE and 0 <= j < BOARD_SIZE and (i, j) not in evaluated:
                        dist = abs(i - center) + abs(j - center)
                        if dist <= 2:
                            score += (3 - dist) * 5  # 中心位置权重
        
        return score
    
    def _evaluate_board_comprehensive(self, board, player):
        """全面评估棋盘（用于高级难度）
        
        Args:
            board: 当前棋盘状态
            player: 当前玩家
            
        Returns:
            int: 评估分数
        """
        score = self._evaluate_board_efficient(board, player)
        opponent = self.human_player if player == self.player else self.player
        BOARD_SIZE = len(board)
        
        # 补充评估一些战略位置
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] == 0 and self._is_strategic_position(board, i, j):
                    # 评估战略位置
                    score += self.evaluate_position(board, i, j, player) * 0.5
                    score -= self.evaluate_position(board, i, j, opponent) * 0.6  # 防守权重略高
        
        return score
    
    def _is_strategic_position(self, board, row, col):
        """判断位置是否为战略位置
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            
        Returns:
            bool: 是否为战略位置
        """
        # 检查是否靠近边界的关键点
        if row <= 2 or row >= self.board_size - 3 or col <= 2 or col >= self.board_size - 3:
            return False
            
        # 检查是否在对手强势区域附近
        opponent_count = 0
        for dr in range(-2, 3):
            for dc in range(-2, 3):
                r, c = row + dr, col + dc
                if 0 <= r < self.board_size and 0 <= c < self.board_size:
                    if board[r][c] == self.human_player:
                        opponent_count += 1
        
        return opponent_count >= 2
    
    def _is_nearby(self, board, row, col, distance=2):
        """检查指定位置附近是否有棋子
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            distance: 检查距离
            
        Returns:
            bool: 是否附近有棋子
        """
        for i in range(max(0, row - distance), min(len(board), row + distance + 1)):
            for j in range(max(0, col - distance), min(len(board[0]), col + distance + 1)):
                if board[i][j] != 0:
                    return True
        return False
    
    def _is_in_center(self, board, row, col, radius=5):
        """检查指定位置是否在中心区域
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            radius: 中心区域半径
            
        Returns:
            bool: 是否在中心区域
        """
        center = len(board) // 2
        return abs(row - center) <= radius and abs(col - center) <= radius
    
    def _get_move_candidates(self, board):
        """优化版获取候选落子位置，使用集合去重提高效率
        
        Args:
            board: 当前棋盘状态
            
        Returns:
            list: 候选位置列表
        """
        candidates = set()
        BOARD_SIZE = len(board)
        
        # 检查是否有棋子已落下
        has_stones = False
        for row in board:
            if any(cell != 0 for cell in row):
                has_stones = True
                break
        
        # 如果棋盘为空，返回中心位置
        if not has_stones:
            return [(BOARD_SIZE // 2, BOARD_SIZE // 2)]
        
        # 查找已存在棋子的周围位置（2格范围内）
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] != 0:
                    # 检查周围5x5区域
                    for di in range(-2, 3):
                        for dj in range(-2, 3):
                            ni, nj = i + di, j + dj
                            if 0 <= ni < BOARD_SIZE and 0 <= nj < BOARD_SIZE:
                                if board[ni][nj] == 0:
                                    candidates.add((ni, nj))
        
        # 如果候选位置太少，扩展搜索范围
        if len(candidates) < 8:
            for i in range(BOARD_SIZE):
                for j in range(BOARD_SIZE):
                    if board[i][j] == 0:
                        # 计算与最近棋子的距离
                        min_distance = float('inf')
                        for x in range(max(0, i-3), min(BOARD_SIZE, i+4)):
                            for y in range(max(0, j-3), min(BOARD_SIZE, j+4)):
                                if board[x][y] != 0:
                                    distance = abs(x - i) + abs(y - j)
                                    min_distance = min(min_distance, distance)
                        
                        # 如果距离较近，添加到候选
                        if min_distance <= 3:
                            candidates.add((i, j))
        
        return list(candidates)
    
    def _pre_evaluate_candidates(self, board, candidates):
        """预评估候选位置并排序
        
        Args:
            board: 当前棋盘状态
            candidates: 候选位置列表
            
        Returns:
            list: 排序后的候选位置列表，格式为(score, row, col)
        """
        scored_candidates = []
        
        for row, col in candidates:
            # 评估AI在该位置落子的价值
            ai_score = self.evaluate_position(board, row, col, self.player)
            
            # 评估玩家在该位置落子的威胁
            player_score = self.evaluate_position(board, row, col, self.human_player)
            
            # 综合评分（防御权重略高于进攻）
            total_score = ai_score * 0.5 + player_score * 0.5
            
            scored_candidates.append((-total_score, row, col))  # 负数用于升序排序
        
        # 排序候选位置
        scored_candidates.sort()
        
        # 转换回正数分数
        return [(-score, row, col) for score, row, col in scored_candidates]
    
    def _get_move_value(self, board, move, player):
        """
计算单个落子位置的静态评估值，用于移动排序
        
        Args:
            board: 当前棋盘状态
            move: 落子位置 (row, col)
            player: 当前玩家
            
        Returns:
            位置的静态评估值
        """
        # 创建临时棋盘进行评估
        temp_board = [row[:] for row in board]
        temp_board[move[0]][move[1]] = player
        
        # 只计算与该位置相关的评估，而不是整个棋盘
        score = 0
        directions = [(0, 1), (1, 0), (1, 1), (1, -1)]
        
        for dx, dy in directions:
            # 检查该方向上的模式
            score += self._evaluate_line_at_position(temp_board, move[0], move[1], dx, dy, player)
            
        # 对对手也进行评估，考虑防守价值
        opponent = 2 if player == 1 else 1
        opponent_board = [row[:] for row in board]
        opponent_board[move[0]][move[1]] = opponent
        
        for dx, dy in directions:
            # 检查对手在该位置的威胁
            score -= self._evaluate_line_at_position(opponent_board, move[0], move[1], dx, dy, opponent) * 0.5
            
        return score
    
    def _evaluate_line_at_position(self, board, row, col, dx, dy, player):
        """
评估特定位置和方向的棋子模式
        
        Args:
            board: 当前棋盘状态
            row: 行坐标
            col: 列坐标
            dx: 行方向
            dy: 列方向
            player: 当前玩家
            
        Returns:
            该位置在该方向的评分
        """
        score = 0
        # 简单地检查一些关键模式
        # 1. 检查是否形成活四或冲四
        if self._check_pattern(board, row, col, dx, dy, player, 4):
            score += 1000
        # 2. 检查是否形成活三或冲三
        elif self._check_pattern(board, row, col, dx, dy, player, 3):
            score += 100
        # 3. 检查是否形成活二或冲二
        elif self._check_pattern(board, row, col, dx, dy, player, 2):
            score += 10
        
        return score
    
    def _check_pattern(self, board, row, col, dx, dy, player, length):
        """
检查特定位置是否形成指定长度的模式
        
        Args:
            board: 当前棋盘状态
            row: 行坐标
            col: 列坐标
            dx: 行方向
            dy: 列方向
            player: 当前玩家
            length: 模式长度
            
        Returns:
            是否形成该模式
        """
        # 简化的模式检查逻辑
        count = 1  # 当前位置已落子
        
        # 向正方向检查
        for i in range(1, 5):
            new_row, new_col = row + i * dx, col + i * dy
            if (0 <= new_row < self.board_size and 0 <= new_col < self.board_size and 
                board[new_row][new_col] == player):
                count += 1
            else:
                break
        
        # 向反方向检查
        for i in range(1, 5):
            new_row, new_col = row - i * dx, col - i * dy
            if (0 <= new_row < self.board_size and 0 <= new_col < self.board_size and 
                board[new_row][new_col] == player):
                count += 1
            else:
                break
        
        return count >= length
        
    def _minimax_with_ab_pruning(self, board, depth, is_maximizing, alpha, beta, prune_factor=0.8):
        """
带Alpha-Beta剪枝的极小极大搜索算法

        Args:
            board: 当前棋盘状态
            depth: 搜索深度
            is_maximizing: 是否为最大化玩家
            alpha: Alpha值（当前最大下界）
            beta: Beta值（当前最小上界）
            prune_factor: 剪枝因子，控制剪枝激进程度
            
        Returns:
            int: 评估分数
        """
        # 计算棋盘的哈希值作为置换表的键
        board_hash = self._get_board_hash(board)
        player = self.player if is_maximizing else self.human_player
        
        # 检查置换表中是否有缓存的结果
        if board_hash in self.transposition_table:
            tt_entry = self.transposition_table[board_hash]
            tt_depth, tt_score, tt_flag = tt_entry
            
            # 如果缓存的深度大于等于当前深度，则可以使用缓存的结果
            if tt_depth >= depth:
                if tt_flag == self.TT_EXACT:
                    return tt_score
                elif tt_flag == self.TT_LOWER and tt_score > alpha:
                    alpha = tt_score
                elif tt_flag == self.TT_UPPER and tt_score < beta:
                    beta = tt_score
                    
                # 如果alpha >= beta，可以提前剪枝
                if alpha >= beta:
                    return tt_score
        
        if depth == 0:
            current_player = self.player if is_maximizing else self.human_player
            score = self.evaluate_board(board, current_player)
            # 存储到置换表
            self.transposition_table[board_hash] = (depth, score, self.TT_EXACT)
            return score
        
        # 获取并预评估候选位置
        candidates = self._get_move_candidates(board)
        scored_candidates = []
        
        # 使用更高效的移动排序
        player = self.player if is_maximizing else self.human_player
        scored_candidates = [(self._get_move_value(board, (row, col), player), row, col) 
                            for row, col in candidates if board[row][col] == 0]
        
        # 排序：最大值优先
        scored_candidates.sort(reverse=True)
        
        # 转换为有序候选位置列表
        ordered_candidates = [(row, col) for _, row, col in scored_candidates]
        
        # 限制考虑的候选数量
        ordered_candidates = ordered_candidates[:int(len(ordered_candidates) * prune_factor) or 1]
        
        if is_maximizing:
            max_score = -float('inf')
            for row, col in ordered_candidates:
                if board[row][col] == 0:
                    board[row][col] = self.player  # AI落子
                    score = self._minimax_with_ab_pruning(board, depth - 1, False, alpha, beta, prune_factor)
                    board[row][col] = 0  # 撤销
                    max_score = max(max_score, score)
                    alpha = max(alpha, score)
                    
                    # Alpha-Beta剪枝
                    if beta <= alpha:
                        break
            return max_score if max_score != -float('inf') else 0
        else:
            min_score = float('inf')
            for row, col in ordered_candidates:
                if board[row][col] == 0:
                    board[row][col] = self.human_player  # 玩家落子
                    score = self._minimax_with_ab_pruning(board, depth - 1, True, alpha, beta, prune_factor)
                    board[row][col] = 0  # 撤销
                    min_score = min(min_score, score)
                    beta = min(beta, score)
                    
                    # Alpha-Beta剪枝
                    if beta <= alpha:
                        break
            
            # 将结果存储到置换表
            tt_flag = self.TT_EXACT
            if min_score <= alpha:
                tt_flag = self.TT_UPPER
            elif min_score >= beta:
                tt_flag = self.TT_LOWER
            
            self.transposition_table[board_hash] = (depth, min_score, tt_flag)
            return min_score if min_score != float('inf') else 0
    
    def _get_board_hash(self, board):
        """获取棋盘状态的哈希值，用于置换表
        
        Args:
            board: 棋盘状态
            
        Returns:
            int: 棋盘的哈希值
        """
        # 将棋盘转换为元组的元组，以便可以哈希
        return hash(tuple(tuple(row) for row in board))
    
    def minimax(self, board, depth, alpha, beta, is_maximizing, start_time, max_time, last_move=None):
        """优化版极小极大搜索算法，带Alpha-Beta剪枝和时间控制
        
        Args:
            board: 棋盘状态
            depth: 当前搜索深度
            alpha: Alpha值
            beta: Beta值
            is_maximizing: 是否为极大方
            start_time: 搜索开始时间
            max_time: 最大搜索时间
            last_move: 最后落子位置，用于增量评估
            
        Returns:
            tuple: (最佳分数, 最佳落子位置)
        """
        # 检查时间是否已超过限制
        if time.time() - start_time > max_time:
            # 时间到，返回当前评估值
            current_player = self.player if is_maximizing else self.human_player
            score = self.evaluate_board(board, current_player, last_move)
            if not is_maximizing:
                score = -score
            return score, None
        
        # 检查置换表
        board_hash = self._get_board_hash(board)
        if board_hash in self.transposition_table:
            entry = self.transposition_table[board_hash]
            if entry['depth'] >= depth:
                if entry['type'] == 'exact':
                    return entry['score'], entry['best_move']
                elif entry['type'] == 'lower_bound':
                    alpha = max(alpha, entry['score'])
                elif entry['type'] == 'upper_bound':
                    beta = min(beta, entry['score'])
                
                if alpha >= beta:
                    return entry['score'], entry['best_move']
        
        # 到达搜索深度时返回评估值
        if depth == 0:
            current_player = self.player if is_maximizing else self.human_player
            score = self.evaluate_board(board, current_player, last_move)
            if not is_maximizing:
                score = -score
            
            # 存入置换表
            self.transposition_table[board_hash] = {
                'depth': depth,
                'score': score,
                'type': 'exact',
                'best_move': None
            }
            return score, None
        
        # 生成所有可能的落子位置
        possible_moves = self._get_move_candidates(board)
        
        # 预评估并排序候选位置
        scored_candidates = []
        player = self.player if is_maximizing else self.human_player
        
        for row, col in possible_moves:
            if board[row][col] == 0:
                # 预评估位置
                score = self.evaluate_position(board, row, col, player)
                scored_candidates.append((-score if is_maximizing else score, row, col))
        
        # 排序候选位置
        scored_candidates.sort()
        ordered_candidates = [(row, col) for _, row, col in scored_candidates]
        
        # 根据剪枝因子限制候选数量
        ordered_candidates = ordered_candidates[:int(len(ordered_candidates) * self.prune_factor) or 1]
        
        if not ordered_candidates:
            return 0, None  # 平局
        
        best_move = None
        
        if is_maximizing:
            max_score = -math.inf
            for row, col in ordered_candidates:
                if board[row][col] == 0:
                    # 模拟落子
                    board[row][col] = self.player
                    
                    # 递归搜索
                    score, _ = self.minimax(board, depth - 1, alpha, beta, False, start_time, max_time, (row, col))
                    
                    # 撤销落子
                    board[row][col] = 0
                    
                    # 更新最大值
                    if score > max_score:
                        max_score = score
                        best_move = (row, col)
                    
                    # Alpha-Beta剪枝
                    alpha = max(alpha, score)
                    if beta <= alpha:
                        break
            
            # 存入置换表
            entry_type = 'exact'
            if max_score <= alpha:
                entry_type = 'upper_bound'
            elif max_score >= beta:
                entry_type = 'lower_bound'
                
            self.transposition_table[board_hash] = {
                'depth': depth,
                'score': max_score,
                'type': entry_type,
                'best_move': best_move
            }
            
            return max_score, best_move
        else:
            min_score = math.inf
            for row, col in ordered_candidates:
                if board[row][col] == 0:
                    # 模拟落子
                    board[row][col] = self.human_player
                    
                    # 递归搜索
                    score, _ = self.minimax(board, depth - 1, alpha, beta, True, start_time, max_time, (row, col))
                    
                    # 撤销落子
                    board[row][col] = 0
                    
                    # 更新最小值
                    if score < min_score:
                        min_score = score
                        best_move = (row, col)
                    
                    # Alpha-Beta剪枝
                    beta = min(beta, score)
                    if beta <= alpha:
                        break
            
            # 存入置换表
            entry_type = 'exact'
            if min_score <= alpha:
                entry_type = 'upper_bound'
            elif min_score >= beta:
                entry_type = 'lower_bound'
                
            self.transposition_table[board_hash] = {
                'depth': depth,
                'score': min_score,
                'type': entry_type,
                'best_move': best_move
            }
            
            return min_score, best_move
    
    def find_best_move(self, board, max_time=None, **kwargs):
        """优化版寻找最佳落子位置，整合迭代加深搜索和时间管理
        
        Args:
            board: 当前棋盘状态
            max_time: 最大思考时间（秒）
            **kwargs: 额外参数
                use_alpha_beta: 是否使用Alpha-Beta剪枝
                prune_factor: 剪枝因子
                max_candidates: 最大候选位置数
                
        Returns:
            tuple: 最佳落子位置(row, col)
        """
        # 使用配置中的时间限制，如果没有指定
        if max_time is None:
            max_time = self.config["max_time"]
        
        # 应用额外参数
        use_alpha_beta = kwargs.get('use_alpha_beta', self.use_alpha_beta)
        prune_factor = kwargs.get('prune_factor', self.prune_factor)
        max_candidates = kwargs.get('max_candidates', self.max_candidates)
        
        start_time = time.time()
        best_move = None
        best_score = -float('inf')
        
        # 清空置换表
        self.transposition_table.clear()
        
        # 动态时间控制：检查当前局面是否存在紧急威胁
        threat_level = self._check_threat_level(board)
        
        # 根据威胁级别调整时间分配
        if threat_level >= 8:  # 严重威胁（如对手四连）
            dynamic_time_limit = max_time * 1.5  # 增加50%时间
        elif threat_level >= 5:  # 中度威胁（如对手活三）
            dynamic_time_limit = max_time * 1.2  # 增加20%时间
        else:
            dynamic_time_limit = max_time
        
        # 根据当前局面复杂度动态调整搜索深度
        complexity = self._estimate_board_complexity(board)
        adjusted_max_depth = min(self.max_depth, self.min_depth + complexity)
        
        # 记录每个深度搜索的时间
        depth_times = []
        
        # 迭代加深搜索
        for depth in range(self.min_depth, adjusted_max_depth + 1):
            # 计算该深度允许的剩余时间
            elapsed_time = time.time() - start_time
            remaining_time = dynamic_time_limit - elapsed_time
            
            # 如果剩余时间不足，跳出循环
            if remaining_time <= 0.1:  # 保留0.1秒用于最后处理
                break
                
            # 为当前深度分配时间
            if depth_times:
                # 基于前一深度的时间估计当前深度需要的时间
                prev_time = depth_times[-1]
                estimated_time = prev_time * 2  # 假设每次深度增加，时间翻倍
                if remaining_time < estimated_time * 0.7:  # 如果剩余时间不足估计时间的70%
                    break
                
                # 分配时间给当前深度
                current_depth_time = min(estimated_time * 1.5, remaining_time * 0.8)
            else:
                # 第一次搜索，分配较多时间
                current_depth_time = remaining_time * 0.5
            
            # 确保至少有少量时间进行搜索
            current_depth_time = max(current_depth_time, 0.1)
            
            # 开始当前深度的搜索
            depth_start_time = time.time()
            
            if use_alpha_beta:
                # 使用带Alpha-Beta剪枝的方法
                # 获取候选位置
                candidates = self._get_move_candidates(board)
                
                # 预评估并排序候选位置
                scored_candidates = self._pre_evaluate_candidates(board, candidates)
                
                # 限制候选数量
                scored_candidates = scored_candidates[:max_candidates]
                
                for score, row, col in scored_candidates:
                    # 检查时间限制
                    if time.time() - depth_start_time > current_depth_time:
                        break
                    
                    # 复制棋盘进行模拟
                    board_copy = copy.deepcopy(board)
                    board_copy[row][col] = self.player  # AI落子
                    
                    # 使用Alpha-Beta剪枝搜索
                    current_score = -self._minimax_with_ab_pruning(
                        board_copy, 
                        depth - 1, 
                        False, 
                        -float('inf'), 
                        float('inf'), 
                        prune_factor
                    )
                    
                    # 更新最佳位置
                    if current_score > best_score:
                        best_score = current_score
                        best_move = (row, col)
                        
                        # 对于高级难度，如果找到明显的好棋，提前返回
                        if self.config["eval_complexity"] in ["high", "highest"] and best_score > 50000:
                            return best_move
            else:
                # 使用传统的minimax方法（带置换表优化）
                # 复制棋盘，避免修改原棋盘
                board_copy = copy.deepcopy(board)
                try:
                    score, current_best = self.minimax(
                        board_copy, 
                        depth, 
                        -math.inf, 
                        math.inf, 
                        True, 
                        depth_start_time, 
                        depth_start_time + current_depth_time
                    )
                    
                    # 如果找到了有效移动，更新最佳移动
                    if current_best:
                        best_move = current_best
                        best_score = score
                        
                        # 对于高级难度，如果找到明显的好棋，提前返回
                        if self.config["eval_complexity"] in ["high", "highest"] and score > 50000:
                            break
                except Exception:
                    # 如果搜索超时或出错，继续下一个深度
                    continue
            
            # 记录当前深度的搜索时间
            depth_time = time.time() - depth_start_time
            depth_times.append(depth_time)
        
        # 如果没有找到最佳移动，返回中心点
        if best_move is None:
            return len(board) // 2, len(board) // 2
        
        return best_move
    
    def _check_threat_level(self, board):
        """
        检查当前局面的威胁级别
        
        Args:
            board: 当前棋盘状态
            
        Returns:
            int: 威胁级别（0-10），数字越大威胁越严重
        """
        # 检查对手是否有严重威胁
        opponent = self.human_player
        threat_level = 0
        
        # 搜索整个棋盘，寻找威胁模式
        for row in range(self.board_size):
            for col in range(self.board_size):
                if board[row][col] == opponent:
                    # 检查四个方向
                    for dx, dy in self.directions:
                        line_info = self._analyze_line_pattern(board, row, col, dx, dy, opponent)
                        
                        # 根据模式确定威胁级别
                        if line_info['consecutive'] >= 4:
                            return 10  # 四连，最高威胁
                        elif line_info['consecutive'] == 3 and line_info['open_ends'] == 2:
                            return 8  # 活三，高威胁
                        elif line_info['consecutive'] == 3 and line_info['open_ends'] == 1:
                            threat_level = max(threat_level, 5)  # 冲三，中度威胁
                        elif line_info['consecutive'] == 2 and line_info['open_ends'] == 2:
                            threat_level = max(threat_level, 3)  # 活二，轻度威胁
        
        # 检查自己是否有进攻机会
        for row in range(self.board_size):
            for col in range(self.board_size):
                if board[row][col] == 0:  # 空位
                    # 模拟落子
                    board[row][col] = self.player
                    
                    # 检查四个方向
                    for dx, dy in self.directions:
                        line_info = self._analyze_line_pattern(board, row, col, dx, dy, self.player)
                        
                        # 根据模式调整威胁级别
                        if line_info['consecutive'] >= 4:
                            threat_level = max(threat_level, 9)  # 即将四连，非常紧急
                        elif line_info['consecutive'] == 3 and line_info['open_ends'] == 2:
                            threat_level = max(threat_level, 7)  # 即将活三，紧急
                    
                    # 撤销落子
                    board[row][col] = 0
        
        return threat_level
    
    def _estimate_board_complexity(self, board):
        """估计当前棋盘的复杂度
        
        Args:
            board: 棋盘状态
            
        Returns:
            int: 复杂度等级（0-3）
        """
        BOARD_SIZE = len(board)
        
        # 计算棋盘上的棋子数量
        piece_count = sum(1 for row in board for cell in row if cell != 0)
        
        # 计算冲突点数量（双方棋子接近的区域）
        conflict_count = 0
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] != 0 and self._has_opponent_nearby(board, i, j):
                    conflict_count += 1
        
        # 计算威胁数量（高价值棋型）
        threat_count = 0
        for i in range(BOARD_SIZE):
            for j in range(BOARD_SIZE):
                if board[i][j] == 0:
                    # 检查该位置的威胁级别
                    ai_score = self.evaluate_position(board, i, j, self.player)
                    player_score = self.evaluate_position(board, i, j, self.human_player)
                    if ai_score > 100 or player_score > 100:
                        threat_count += 1
        
        # 根据棋子数量、冲突数量和威胁数量评估复杂度
        if piece_count < 10:
            return 0  # 开局阶段，复杂度低
        elif piece_count < 20:
            return 1  # 中局初期
        elif conflict_count < 5 and threat_count < 3:
            return 2  # 中局
        else:
            return 3  # 复杂局面
    
    def _has_opponent_nearby(self, board, row, col, distance=2):
        """检查指定位置附近是否有对手棋子
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            distance: 检查距离
            
        Returns:
            bool: 是否附近有对手棋子
        """
        current_player = board[row][col]
        if current_player == 0:
            return False
        
        opponent = self.human_player if current_player == self.player else self.player
        
        for i in range(max(0, row - distance), min(self.board_size, row + distance + 1)):
            for j in range(max(0, col - distance), min(self.board_size, col + distance + 1)):
                if board[i][j] == opponent:
                    return True
        return False
    
    def check_win(self, board, row, col):
        """检查指定位置落子后是否获胜
        
        Args:
            board: 棋盘状态
            row: 行索引
            col: 列索引
            
        Returns:
            bool: 是否获胜
        """
        player = board[row][col]
        if player == 0:
            return False
        
        # 检查四个方向
        for dr, dc in self.directions:
            count = 1  # 已包含当前落子
            
            # 正方向
            r, c = row + dr, col + dc
            while (0 <= r < self.board_size and 0 <= c < self.board_size and 
                   board[r][c] == player):
                count += 1
                r += dr
                c += dc
            
            # 反方向
            r, c = row - dr, col - dc
            while (0 <= r < self.board_size and 0 <= c < self.board_size and 
                   board[r][c] == player):
                count += 1
                r -= dr
                c -= dc
            
            if count >= 5:
                return True
        
        return False

# 测试代码（用于验证AI功能）
def test_ai_player():
    """测试AI玩家功能"""
    ai = AIPlayer(difficulty="medium")
    
    # 创建一个测试棋盘
    board = [[0 for _ in range(15)] for _ in range(15)]
    
    # 测试评估函数
    print("测试评估函数...")
    score = ai.evaluate_board(board, 2)
    print(f"空棋盘AI方评分: {score}")
    
    # 测试最佳落子
    print("\n测试寻找最佳落子...")
    best_move = ai.find_best_move(board)
    print(f"空棋盘最佳落子位置: {best_move}")
    
    # 测试有棋子的情况
    board[7][7] = 1  # 玩家在中心落子
    best_move = ai.find_best_move(board)
    print(f"玩家在中心落子后，AI最佳落子位置: {best_move}")

if __name__ == "__main__":
    test_ai_player()
